The Internet has revolutionized the way we share information. For instance, the various personal and professional social media sites on the Internet allow users to seamlessly connect to friends and colleagues to share personal and professional experiences. In another example, individuals and businesses often use the Internet to facilitate sharing a wide range of information and data. While current digital technologies simplify the sharing of information, the information may be personal or sensitive.
A comparison of two sets of data elements may be beneficial before two entities decide to share personal or sensitive information. The comparison of the two sets of data elements may involve computing the intersection of the two sets of data elements. For example, users of a social media site may want to determine who their common friends or acquaintances are before accepting a follow or friend request. In another example, two business entities may wish to determine the number or identities of common customers before entering into a business relationship. In yet another example, a medical entity may need to perform data analysis on two sets of data elements to determine an intersection of the data elements, which may include patient related information, without violating patient privacy.
Private set intersection may enable entities to compute the intersection of data elements included within their respective sets of data elements without disclosing any information about the data elements contained in the sets of data elements. For example, in a client/server environment, the client may ascertain the intersection of elements within the sets of data elements, while the server does not ascertain the intersection of data elements within the sets of data elements. Private set intersection has numerous real-world applications including social media contact sharing and privacy preserving data mining, such as those performed by medical and/or government entities. More specifically, private set intersection allows two entities E1 and E2 to find the intersection of two sets of data elements S1 and S2 without having to disclose the sets of data elements to each other. In other words, using private set intersection the two entities E1 and E2 may find the intersection I=S1 ∩S2 of their sets without learning information about the other party's set of data elements beyond the intersection I.
While conventional private set intersection techniques allow entities to find the intersection of sets of data elements, those conventional private set intersection techniques have some inherent inefficiencies. For example, conventional private set intersection techniques may require the involved entities to exchange a large amount of ciphertext information related to the sets of data elements. This exchange of the large amount of ciphertext information may impede speed and efficiency in calculating the intersection of the sets of data elements and disseminating the intersection of the sets of data elements. Furthermore, conventional private set intersection techniques may not efficiently encrypt and communicate data strings that exceed 32 bits. Specifically, conventional private set intersection techniques that encrypt data strings that exceed the 32 bits create excessively large ciphertext strings that require enormous communication bandwidth and/or storage at the receiver of the ciphertext strings. Therefore, efficient techniques for providing private set intersection remain elusive. Specifically, some conventional private set intersection techniques create large encrypted payloads that are inefficient to transfer and consume significant processing resources.
It is with respect to these and other considerations that the disclosure made herein is presented.